#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef int ElementType;

//任务：构造一个链表结构，实现对链表的一些操作
//1.构造一个链表 第一步构造节点 第二步形成链表
//1.1构造节点
typedef struct node{
    //1.数据项
    ElementType data;
    //2.地址项
    struct node *next;
} Node;

//构造链表
/*
 * 函数名：creat() init()
 * 输入:没有输入，直接在函数里调动scanf()来获取数据
 * 输出：头结点
 * */
Node *creat(){
    //1.头结点
    Node *head =NULL;
    head = malloc(sizeof(Node*));
    //2.真正用来存储数据项的节点
    Node *current =NULL;
    current = malloc(sizeof(Node*));
    Node *new =NULL;

    //实现循环
    current =head;
    ElementType data;

    //循环读取数据
    printf("请输入一组整数，-1作为结束的标志\n");
    while(scanf("%d",&data)&&(data!=-1)){
        new = malloc(sizeof(Node*));
        //根据元素对新节点进行赋值
        new->data=data;
        //当前节点指向新节点
        current->next=new;
        //当前节点 后移
        current = new;

    }

    //3.NULl，最后节点指向NULL
    current->next=NULL;
    //返回
    return  head;
}
//3 查找函数
//3.1根据位置返回节点
/*
 * 函数名：findByIndex()
 * 输入：链表 （头节点）,pos
 * 输出：节点
 * */
Node* findByIndex(Node *head,int pos){
    //循环找
    //定义一个用来后移的指针
    Node *current = head->next;

    //开始循环，循环的结束条件：1.i=pos 2.current==NULL
    int i =1;
     while((current!=NULL)&&(i<pos)){
         current=current->next;
         i++;
     }
     //结束循环
     if(current==NULL){
        // printf("没有对应的节点");
         //return NULL;
         return current;
     }
     if(i==pos){
         return  current;
     }
    //return current;
}
//3.2 根据元素返回节点
Node * findByValue(Node*head,ElementType value){
    Node* current =NULL;
    current =head->next;
    while((current!=NULL)&&(current->data!=value)){
        current = current->next;

    }
    return  current;

}

//4.插入
/*
 * 函数名insert
 *
 * 输入：链表，待插入位置，插入元素
 * 输出bool int
 * */
//alter+shift+enter
bool insert(Node *head,int pos,ElementType data){

    if(head==NULL||pos<0){
        printf("参数有误\n");
        return false;
    }
    //插入的步骤：1.创建新节点，用来存放数据
    Node* newNode = malloc(sizeof (Node));
    newNode->data=data;
    if(pos==1){

       /* //2.找到待插入节点的前一个节点
        Node *preNode =head;
        //3.找到待插入位置节点
        Node* currNode = head->next;//curr=head.next*/
        //4.将新节点指向当前节点
        newNode->next=head->next;
        //5.将前位置节点指向新节点
        head->next=newNode;

    } else{
        //2.找到待插入节点的前一个节点
        Node *preNode = findByIndex(head,pos-1);
        //3.找到待插入位置节点
        Node* currNode = preNode->next;
        //4.将新节点指向当前节点
        newNode->next=currNode;
        //将前位置节点指向新节点
        preNode->next=newNode;

    }
    return true;


}
//5.删除


int main() {

    //构造节点
    //1.head
    Node *head =NULL;
    head = malloc(sizeof(Node*));
    //2.中间的存储数据的节点
    Node *first =NULL;
    first = malloc(sizeof(Node*));
    Node *second =NULL;
    second = malloc(sizeof(Node*));
    Node *third =NULL;
    third = malloc(sizeof(Node*));
    first->data=1;
    second->data=2;
    third->data=3;

    //3.节点的结束NULL
    //链接链表
    head->next=first;
    first->next=second;
    second->next=third;
    third->next=NULL;

    //自动初始化
    Node *head_list;
    head_list = creat();

    Node *tmpNode= NULL;
    tmpNode= head_list->next;
    while (tmpNode!=NULL){
        printf("%d ",tmpNode->data);
        tmpNode=tmpNode->next;
    }
    printf("测试查找\n");
    int pos = 3;
    printf("位置%d的节点是:\n",pos);
    Node *node= findByIndex(head_list,pos);
    printf("%d",node->data);

   // bool f2 = insert(head_list,3,45);

    //printf("Hello, World!\n");
    return 0;
}
